#include <stdio.h>
#include <stdlib.h>
void solve(int m, int n) {
	int s = 0;
	while (n) {
		s += n / m;
		n /= m;
	}
	printf("%d\n", s);
}
int main(void) {
	int s, m, n;
	scanf("%d", &s);
	while (s--) {
		scanf("%d%d", &n, &m);
		solve(m, n);
	}
	return EXIT_SUCCESS;
}
